package hot_100;

/**
 * @author: Darven
 * @createTime: 2025-09-22  09:55
 * @description: TODO
 */
public class P76 {
    public static void main(String[] args) {
        P76 p76 = new P76();
        System.out.println(p76.minWindow("bba", "ab"));
        ;
//        System.out.println( p76.minWindow("a", "a"));;
//        System.out.println(p76.isContainer("BANC", "ABC"));
    }

//    public String minWindow(String s, String t) {
//        int tLength = t.length();
//        int sLength = s.length();
//
//        if(tLength>sLength){
//            return "";
//        }
//
//        // 外层滑动窗口个数
//        for(int i=tLength;i<=sLength;i++){
//            for(int z=0,x=i;x<=sLength;x++,z++){
//                String substring = s.substring(z, x);
//                if(isContainer(substring, t)){
//                    return substring;
//                }
//            }
//        }
//        return "";
//    }

//    public String minWindow(String s, String t) {
//        int tLength = t.length();
//        int sLength = s.length();
//
//        if (tLength > sLength) {
//            return "";
//        }
//        String ans = "";
//        // 使用滑动窗口
//        for (int i = 0, j = tLength; j <= sLength; ) {
//            String sub = s.substring(i, j);
//            if (isContainer(sub, t)) {
//                if (ans.isEmpty()) {
//                    ans = sub;
//                } else {
//                    if (sub.length() < ans.length()) {
//                        ans = sub;
//                    }
//                    i++;
//                }
//            }else {
//                j++;
//            }
//
//        }
//        return ans;
//    }

    //    public boolean isContainer(String a, String b) {
//        int[] count = new int[256];
//
//        for (char c : a.toCharArray()) {
//            count[c]++;
//        }
//
//        for (char c : b.toCharArray()) {
//            if (count[c] == 0) {
//                return false;
//            }
//            count[c]--;
//        }
//
//        return true;
//    }
//    public String minWindow(String s, String t) {
//        int k = t.length();
//        int sLength = s.length();
//
//        if (k > sLength) {
//            return "";
//        }
//
//        int[] needs = new int[256];
//        int left = 0;
//        int right = 0;
//        int start = 0;
//        int minLen = Integer.MAX_VALUE;
//
//        // init needs[]
//        for (char c : t.toCharArray()) {
//            needs[c]++;
//        }
//
//
//        while (right < sLength) {
//            char a = s.charAt(right);
//            right++;
//
//            if (needs[a] > 0) {
//                k--;
//            }
//            needs[a]--;  //无论是否需要，都要减掉，这样非t就是<0
//
//            while (k == 0) {
//                if (minLen >= right - left + 1) {
//                    start = left;
//                    minLen = right - left+1;
//                }
//                needs[s.charAt(left)]++;
//                if (needs[s.charAt(left)] > 0) {
//                    k++;
//                }
//
//                left++;
//            }
//        }
//
//        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, minLen+start-1);
//    }













































    public String minWindow(String s, String t) {
        int sLen=s.length();
        int tLen=t.length();
        // 构造t的哈希表
        int[] needs=new int[128];
        int k=tLen;
        // 有的值就是1，没有的值是0
        for(int i=0;i<tLen;i++){
            needs[t.charAt(i)]++;
        }
        // 滑动窗口思想，通过右边不断移动，找到t中所有种类，然后在进行记录，左边进行++
        int l=0,r=0;
        int minLen=Integer.MAX_VALUE;
        int start=0;
        while (r<sLen){
            char c = s.charAt(r);
            r++;
            // 如果当前字符在t中，种类-1
            if(needs[c]>0){
                k--;
            }
            // 每次都减少
            needs[c]--;
            // k为0，说明所有t都在s里面
            while(k==0){
                // 计算左边右边的坐标，记录小赖
                if(minLen>r-l+1){
                    minLen=r-l+1;
                    start=l;
                }
                // 直接++，如果是大于0，说明是t里面的，否则就是非t部分
                needs[t.charAt(l)]++;
                if(needs[t.charAt(l)]>0){
                    k++;
                }
                l++;
            }
        }
        return minLen==Integer.MAX_VALUE?"":s.substring(start, start+minLen-1);
    }
}
